package com.example.design.leetcode.dynamic;

//剑指 Offer 46. 把数字翻译成字符串
//    给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
//
//    示例 1:
//    输入: 12258
//    输出: 5
//    解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

public class Practice44 {

    // 状态定义：f(n)表示第n个元素有f(n)种翻译

    // 状态定义方程：
    //  n-1 与 n两数组合在[10-25]之间： f(n) = f(n-2) + f(n-1)
    // 为什么是这是f(n-2) + f(n-1)公式呢？
    // 当(n-1)与n组合翻译时，相当于他两绑定了，为一个数，所以，组合翻译时的次数等于f(n-2)
    // 当n单独翻译时，次数就等于f(n-1)了，比如：02  0的翻译次数只有一次；第二个元素2的翻译次数还是只有一次
    // n-1 与 n两数组合不在[10-25]之间： f(n) = f(n-1)

    // 边界 f(0) = 1 翻译第0个元素，什么也不做也是一种方式 f(1) =1

    public int translateNum(int num) {
        String numStr = String.valueOf(num);

        int[] temp = new int[numStr.length() + 1];

        temp[0] = 1;
        temp[1] = 1;

        for (int i = 2; i <= numStr.length(); i++) {
            String s = numStr.substring(i - 2, i);
            Integer integer = Integer.valueOf(s);
            if (10 <= integer && integer <=25) {
                temp[i] = temp[i -1] + temp[i-2];
            } else {
                temp[i] = temp[i -1];
            }
        }
        return temp[numStr.length()];
    }
}